package yz.com.javautil.roadNetwork;

import java.util.Vector;

/**
 * 稠密图实现
 * 参考资料：https://www.runoob.com/data-structures/graph-theory-path.html
 *
 * @author runoob
 */
public class DenseGraphImpl implements Graph {
    /**
     * 节点数
     */
    private int nodeNum;
    /**
     * 边数
     */
    private int edgeNum;
    /**
     * 是否为有向图
     */
    private boolean directed;
    /**
     * 图的具体数据
     */
    private boolean[][] graph;

    /**
     * 构造函数
     * g初始化为n*n的布尔矩阵, 每一个g[i][j]均为false, 表示没有任和边, false为boolean型变量的默认值
     *
     * @param nodeNum        边数
     * @param directed 是否有向
     */
    public DenseGraphImpl(int nodeNum, boolean directed) {
        assert nodeNum >= 0;
        this.nodeNum = nodeNum;
        // 初始化没有任何边
        this.edgeNum = 0;
        this.directed = directed;
        graph = new boolean[nodeNum][nodeNum];
    }

    @Override
    public int getNodeNum() {
        return nodeNum;
    }

    @Override
    public int getEdgeNum() {
        return edgeNum;
    }

    @Override
    public void addEdge(int v, int w) {
        assert v >= 0 && v < nodeNum;
        assert w >= 0 && w < nodeNum;
        if (hasEdge(v, w)) {
            return;
        }
        graph[v][w] = true;
        // 是否有向
        if (!directed) {
            graph[w][v] = true;
        }
        edgeNum++;
    }

    @Override
    public boolean hasEdge(int v, int w) {
        assert v >= 0 && v < nodeNum;
        assert w >= 0 && w < nodeNum;
        return graph[v][w];
    }

    @Override
    public Vector<Integer> getAdjacentEdge(int v) {
        assert v >= 0 && v < nodeNum;
        Vector<Integer> adjacentEdgeVector = new Vector<>();
        for (int i = 0; i < nodeNum; i++) {
            if (graph[v][i]) {
                adjacentEdgeVector.add(i);
            }
        }
        return adjacentEdgeVector;
    }

    @Override
    public void show() {
        for (int i = 0; i < nodeNum; i++) {
            for (int j = 0; j < nodeNum; j++) {
                System.out.print(graph[i][j] + "\t");
            }
            System.out.println();
        }
    }
}
